package com.future;

/**
 * Description: 164. 最大间距(大厂刷题7)
 *
 * @author weiruibai.vendor
 * Date: 2022/7/19 14:15
 */
public class Solution_164 {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 6, 9, 1};
        // [1,10000000]
        nums = new int[]{1, 10000000};
        /**
         * 494767408,862126209,213511142,768240025,631263193,839199222,990848796,214568815,540853864,760724418,980162605,976743981,168965760,680875496,256709197,970953816,948680062,347254784,732201399,786249847,782805044,40906641,674241381,784330934,175502610,731105392,424650824,549764101,986090032,710542549,249208107,448419816,527708664,158499246,223421723,114552457,466978424,821491411,19614107,115389497,902211438,2644108,744489871,897895073,372311214,551142753,933294894,426217662,217504874,983488406,516890023,426853110,971124103
         */
        nums = new int[]{494767408, 862126209, 213511142, 768240025, 631263193, 839199222, 990848796, 214568815, 540853864, 760724418, 980162605, 976743981, 168965760, 680875496, 256709197, 970953816, 948680062, 347254784, 732201399, 786249847, 782805044, 40906641, 674241381, 784330934, 175502610, 731105392, 424650824, 549764101, 986090032, 710542549, 249208107, 448419816, 527708664, 158499246, 223421723, 114552457, 466978424, 821491411, 19614107, 115389497, 902211438, 2644108, 744489871, 897895073, 372311214, 551142753, 933294894, 426217662, 217504874, 983488406, 516890023, 426853110, 971124103};
        System.out.println(maximumGap(nums));
    }


    public static int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Integer min = nums[0];
        Integer max = nums[0];
        Integer N = nums.length;
        for (int i = 0; i < N; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (max == min) {
            // 值都相等
            return 0;
        }
        boolean[] hasNumArr = new boolean[N + 1];
        int[] maxArr = new int[N + 1];
        int[] minArr = new int[N + 1];
        for (Integer num : nums) {
            int index = bucket(num, N, min, max);
            maxArr[index] = hasNumArr[index] ? (Math.max(maxArr[index], num)) : num;
            minArr[index] = hasNumArr[index] ? (Math.min(minArr[index], num)) : num;
            hasNumArr[index] = true;
        }
        int ans = 0;
        int lastMax = maxArr[0];
        for (int i = 1; i < N + 1; i++) {
            if (hasNumArr[i]) {
                ans = Math.max(ans, minArr[i] - lastMax);
                lastMax = maxArr[i];
            }
        }
        return ans;
    }

    /**
     * 必须用long类型，否则会越界
     *
     * @return
     */
    private static int bucket(long num, long N, long min, long max) {
        return (int) ((num - min) * N / (max - min));
    }

}
